

A program spectrum is a set of counters for the execution of given program locations
(although SFL usually only considers hit spectra).
For example, if a function \verb|f| of a program is instrumented,
then during the execution of the program the counter associated with \verb|f| is incremented each time \verb|f| is called.
The available instrumentation passes for generation program spectra are given in Table \ref{t:programspectra}.
Every instrumentation should include the \verb|bypassmain| instrumentation pass 
for the analysis library to be able to handle the instrumented code.
In the next sections the different program spectra are discussed in more detail.


\begin{table}
  \begin{center}
  \begin{tabular}{l|l}
    name & description \\
	\hline
    -spbasicblock & instrument basic blocks \\
	-spfunction & instrument functions \\
	-spdefuse & instrument define-use pairs \\
  \end{tabular}
  \caption{instrumentation passes for generation of program spectra}
  \label{t:programspectra}
  \end{center}
\end{table}



\section{Basic Blocks}

	Basic blocks of code are defined as a sequence of statements with one entry point and one exit point,
	having no jump instructions contained within it.
	Basic blocks can be considered the basic unit of a program with respect to control flow.
	Whether a basic block is executed or not, or the number of times a certain basic block is executed, 
	can give useful information on the influence of this block on a failing execution of the program.
	
	In the basic block instrumentation pass, basic blocks are retrieved from the LLVM intermediate representation.
	It must be noted that the LLVM intermediate code sometimes contains additional basic blocks, 
	due to the generation of additional blocks which do not change the control flow.
	For example, a block is generated by default at the end of a function to contain the function return,
	although that function may consist of a single block of control flow with no branches.
	However, since the set of LLVM basic blocks is always a superset of the usual set of basic blocks,
	the resulting spectrum can be considered equally usable for further analysis.

	Performing basic block instrumentation is done using the \verb|-spbasicblock| option of the \verb|instrument| tool.
	For example,\\
	\verb|  # instrument -spbasicblock -bypassmain textVal.bc -o textVal.ibc|\\
	will instrument basic blocks and will perform the necessary bypass of the main function.

	

\section{Functions}

	The entry of every function in the program can be instrumented.
	Each time a function is called, the corresponding counter will be incremented.
	This can be useful in situations in which a project contains many small functions
	and a function containing the fault must be localized.
	This will not be as accurate as basic block instrumentation, 
	but the overhead will be limited, since there are far less functions
	in a program than there are basic blocks.
	
	Performing function instrumentation is done using the \verb|-spfunction| option of the \verb|instrument| tool.
	For example,\\
	\verb|  # instrument -spfunction -bypassmain textVal.bc -o textVal.ibc|\\
	will instrument every function and will perform the necessary bypass of the main function.
	It must be noted that the order of instrumentation passes is important in this case,
	since the new main function will be instrumented in the case that the \verb|bypassmain|
	instrumentation is performed before the \verb|spfunction| pass.
	This will result in a distorted source code context.
	The rule is that the \verb|bypassmain| is always last in the chain of instrumentation passes.


\section{Def-Use Pairs}

	A variable is defined once in its lifetime.
	This instance of a variable can be used at different locations of the program.
	The def-use spectrum contains a counter associated with each of these \emph{uses}.
	One variable can have multiple uses and therefor have multiple counters in the spectrum.
	Whenever, during the execution of the program, a variable is used, 
	the counter associated with that particular use is incremented.
	
	Performing def-use instrumentation is done using the \verb|-spdefuse| option of the \verb|instrument| tool.
	For example,\\
	\verb|  # instrument -spdefuse -bypassmain textVal.bc -o textVal.ibc|\\
	will instrument every use of declared variables and will perform the necessary bypass of the main function.
	
	Currently, the source code location of these uses are not reflected well in the generated context.
	The results when using this option are, for the time being, harder to interpret.

	
\section{Custom Program Spectra}

	The instrumentation of program points for generating program spectra is not limited to the discussed instrumentations.
	A custom pass can be created to obtain run time information of the program 
	suited to the needs of a specific analysis.
	The technical information needed for implementing custom instrumentation passes 
	is discussed in detail in Appendix \ref{c:WritingInstrumentationPasses}.
	
	
	

	% \begin{exercise}{Basic Block Instrumentation}
	% Compile the source code of RationalSort.c to LLVM byte code containing debug information using the LLVM gcc-frontend:\\
	% \verb|# llvm-gcc -emit-llvm -g -c RationalSort.c -o RationalSort.bc|\\
	% Then, instrument the byte code with basic block spectrum information gathering functionality.
	% Note that bypassing of main is required for instrumentation to have effect:\\
	% \verb|# instrument -spblock -bypassmain RationalSort.bc > RationalSort.ibc|
	% \end{exercise}
	  
	% \begin{exercise}{Inspect Instrumentation}
	% Convert the instrumented byte code back to C code:\\
	% \verb|# llc -march=c RationalSort.ibc -o RationalSort_i.c|\\
	% Inspect the code.
	% Notice that LLVM generates a large amount of extra code when translating LLVM byte code back to C.
	% Locate the \verb|_updateSpectrum| calls in the code.
	% These are the actual points in the program that are instrumented (at the beginning of each basic block).
	% Verify that there is no \verb|main| method and that the original \verb|main| method is replaced by \verb|_main_original|.
	% \end{exercise}
